非對稱式密碼學 - Diffie–Hellman

接下來一樣就是進入數學上～

但這邊的數學比起RSA來要簡單一些，不用一些特別的定理。

我想應該不難理解～

好～廢話不多說，直接進入數學吧！

Diffie–Hellman

我們先記得一個算式：『base^x mod p』。

先解釋一下，base為基底或稱為原根，而p就是『質數』來取模的。

好，那接下來都會落在這個公式上。

先設定A是傳輸訊息的，B是接收的，竊聽為C，竊取者，會獲得公開的訊息。

1. A設定了一個 base ＝ 23 跟 p ＝ 83，然後選了一個秘密的a＝8。
   計算公式『base^a mod p ＝ AP（A Public）』。
   然後把 base 、 p 跟 AP 傳給 B。
   • 公開：
     • base = 23
     • p = 83
     • AP ＝ 63
   • A方：
     • a = 8
2. B收到後，一樣選擇了一個秘密的b＝12，
   先計算『AP^b mod p = APBP（Key）』，
   在計算『base^b mod p = BP（B Public）』，
   然後把 BP 傳送給A。
   • 公開：
     • base = 23
     • p = 83
     • AP ＝ 63
     • BP ＝ 36
   • A方：
     • a = 8
   • B方：
     • b = 12
     • APBP（Key） ＝ 37
3. A接收到BP後計算『BP^a mod = APBP（Key）』。
   • 公開：
     • base = 23
     • p = 83
     • AP ＝ 63
     • BP ＝ 36
   • A方：
     • a = 8
     • APBP（Key） ＝ 37
   • B方：
     • b = 12
     • APBP（Key） ＝ 37

這就完成了交換，獲得了一個Key。

這個原理比較簡單。
base^ab mod p == base^ba mod p = (base^a mod p)^b mod p = (base^b mod p)^a mod p。

那我們假設竊取方來破解，我們先確定自己有的東西：

• 公開：
  • base = 23
  • p = 83
  • AP ＝ 63
  • BP ＝ 36

我們能知道公式『base^(a or b) mod p = (AP or BP)』。
我們能從AP跟BP來得知a跟b嗎？
23為底的應該『乘多少次方』並『取餘數p』才能得到AP或BP？
除了一個一個數字去測試，其實也沒什麼辦法。

這邊就是對數離散問題了。

這邊注意一件事，一般來說其實g不用太大，選2、3就OK了。
（PS. 選擇2是個十分高效的方式，2的n次方在程式中能寫成『2 << n-1』，電腦在做二進制的位移是超級有效率的。）

但p最好要選很高位的質數，最好還是『索菲·熱爾曼質數』，推薦來說最少300位，而a跟b至少100位。

PS. 索菲·熱爾曼質數：
這邊跟大家說下，p為質數，而『p*2-1』如果也是『質數』，那就是安全質數，稱為索菲·熱爾曼質數。
雖然程式驗證很簡單。
但1-10000之間只有190個，機率蠻低的。
在頁面中有機率的公式，而生產出一個索菲·熱爾曼可能花費太多時間。

相比RSA來說，簡單十分多吧～

而我們之前也講過了大質數的生成，之前也講過了。

那接下來我們來看一下DH的另一個數學公式ECC（橢圓曲線密碼學）。

作者的話

說起來這章實在太簡單、太短了，但也因為這樣，要寫加密的程式也不難就是了。

一樣我們來出個挑戰如何？

挑戰

一樣大家也可能會覺得很簡單，因此我也是出了一個挑戰～

其實難度都還好，說真的沒很高～

一樣我把公開的訊息提供出來，然後再給一個加密的訊息，嘗試把它解開吧～。

（還是沒有獎品，但你依然很棒！）

前提

我的訊息是先做utf-8的編碼後，用Python的int.from_bytes轉換成數字。

還原的方法也不難：

plain_text_int（解密後的數字）.to_bytes(24, 'big').decode('utf-8')

加密跟解密的部分就是簡單的做XOR

plain=cipher^Key
cipher=plain^Key

挑戰一

p為60位、a跟b都為30位。
apbp共同金鑰為60位。
p使用『索菲·熱爾曼質數』。

p（60位）：

699486986552554592675767925237638677759118601290809803914121

公開AP（60位）：

170178636557639746210574832413131272865700283634333688294333

公開BP（60位）：

557641745723310355752438291890622301450434353737544727118613

加密後的訊息（60位）：

530292252643122520024900723952166657462747933987144373491010

挑戰二

p為80位、a跟b都為40位。
apbp共同金鑰為80位。
p使用『索菲·熱爾曼質數』。

p（80位）：

73571802714540347494648469868828462984410276164349204652343904219448131175222989

公開AP（80位）：

43032596902668711516531950243873782237650990862403056372872764768404690087242404

公開BP（80位）：

25833323449518720107590783096395275832042421373337646716328462557279431320607779

加密後的訊息（80位）：

56023902093440355627441537359803988043178722411656849671411990827317939123417600

參考資料

迪菲-赫爾曼密鑰交換

索菲·熱爾曼質數